1. Technical Field
The present invention relates to computer graphics generation and display, and more particularly to a hardware assisted method for rendering wire-frame images of tessellated objects with hidden lines either removed or displayed in a different line style than visible lines, and with tessellation edges that are not silhouette edges suppressed.
2. Background Art
Computer graphics display systems typically derive images from stored digital data representative of points in a three-dimensional coordinate system. The points correspond to the vertices of polygons, which, in turn, form the "building blocks" of larger objects which are the ultimate display objects. The vertex data stored in the system's memory includes positional data in a three-dimensional coordinate system in which, for example, the X and Y axes define a view plane and the Z axis represents distances from a viewpoint. In the generation of an actual graphics display, the polygons defining the object to be displayed are projected onto the view plane.
A typical graphics display system's hardware includes a geometric model processor which processes digital data representing coordinates of vertices of the object or objects to be displayed to produce digital data representing a tessellated version of the object or objects, a rasterizer which transforms three-dimensional digital data into two-dimensional digital data and scanconverts the two-dimensional data to produce a depth value for each pixel covered by the object and a color value corresponding to that depth value, a depth buffer in which is stored depth values relating to an object to be displayed, a frame buffer in which pixel color values are stored, and a display screen on which the image is displayed.
Among the types of images which can be produced by a typical graphics display system is a wire-frame image. A wire-frame image consists of line segments on the display screen representing the object, as distinguished from other representations, such as a shaded image. To help clarify a wire-frame representation, curved portions are usually tessellated. Tessellation is the piecewise planar approximation of a curved face by a connected mesh of polygons (or facets). While a tessellated wire-frame image is useful in visualizing objects for a variety of purposes, for example, design, there exists limitations in its current usefulness. The user may wish to remove hidden lines, i.e. lines which could not be seen from a given viewing direction if the object were a solid, or lines obscured by other objects. The user may want to distinguish between visible and hidden lines; visible lines being those which could be seen from a given viewing direction if the object were a solid. The user may also want to treat different categories of lines differently, for example silhouette and intersection edges.
The broad category of tessellation edges encompasses both silhouette and intersection edges. Silhouette edges are those edges whose projection lies on the boundary of the two-dimensional projection of the object onto a view plane from a given viewing direction. Intersection edges are those edges which lie on the boundary between any two adjacent faces of the object. A face is defined as any continuous portion of the object boundary that lies on a single surface. For example, a cube has six faces, and a cylinder has three. Visible edges may be obscured by the faces they lie on due to round-off errors in the scanconversion process. In addition, the foregoing needs must be addressed in real time to be most useful.
Prior art techniques exist which address the problem of hidden line and surface removal. For example, a depth buffer technique is often used in which the depth values for each projected point are determined and compared. For any given display point on the view plane (corresponding to a particular pixel on the view screen) having a corresponding storage location in the depth buffer and the frame buffer of the system, the point chosen for display will be that which is closest to the viewpoint. Thus, for example, in the generation of a shaded image of an object, the points of the polygons closest to the viewpoint will be displayed while those hidden by closer polygons will not. This prior art technique is generally described by Foley, Van Dam, Feiner and Hughes, "Computer Graphics Principles and Practice," second edition, Addison-Wesley Publishing Company, Inc., at 665-72 (1990). These techniques are not directly applicable to the problem of real time hidden line removal in wire-frame displays.
U.S. Pat. No. 4,855,938, "Hidden Line Removal Method With Modified Depth Buffer" issued to Gonzalez-Lopez et al. discloses a method for hidden line removal wherein objects are tessellated into triangles. However, that method requires that each triangle be processed one at a time, and does not address the need to distinguish silhouette edges from other tessellation edges. In addition, that method requires specialized hardware to implement. U.S. Pat. No. 5,043,921, "High Speed Z-Buffer Control" issued to Gonzalez-Lopez et al. discloses a method for removing hidden surfaces which saves pixel values only for those surfaces closest to a given viewpoint. While the present invention utilizes this concept, Gonzalez-Lopez et al. require specialized hardware not necessary in the present invention. Other prior art techniques to remove hidden lines include software solutions which are generally too slow to obtain real-time display. Integration of a software solution into the pipeline architecture typically used in graphics display systems is restricted, since most software solutions rely on face-to-edge adjacency information typically not available in the pipeline.
The problem of distinguishing silhouette edges has recently been addressed by Saito and Takahashi in "Comprehensible Rendering of 3-D Shapes," Computer Graphics 24(4) (Proceedings Siggraph '90) at 197-206. They introduce a two-dimensional image processing technique which highlights shape features and silhouette edges, but does not provide for clarification of the internal structure of a model.
The problem of visible edges being obscured by the faces they lie on was also addressed in U.S. Pat. No. 4,855,938. There, a special value is used to mark pixels where visible edges are to be displayed. While this technique does solve the problem, it requires two passes over each polygon edge and is thus relatively slow for modern graphics needs. Also, it does not address the need to distinguish silhouette edges from other tessellation edges.